public class MyLinkedList {
     static class ListNode{
         public int val;
         public ListNode next;
         public  ListNode prev;

         public ListNode(int val) {
             this.val = val;
         }
     }
     public ListNode head;
     public ListNode last;
     public void addFist(int data){
         ListNode listNode=new ListNode(data);
         if (head==null){
             head=listNode;
             last=listNode;
         }else {
             listNode.next=head;
             head.prev=listNode;
             head=listNode;
         }
     }
     public void addLast(int data){
         ListNode listNode=new ListNode(data);
         if (head==null){
             head=listNode;
             last=listNode;
         }else {
             last.next=listNode;
             listNode.prev=last;
             last=listNode;
         }
     }
     public void indexAdd(int index,int data){
         int size=size();
         if(index<0||index>size){
             System.out.println("下标不合法"+index);
   return;
         }
         if (index==0) {
             addFist(data);
             return;
         }
         if (index==size){
             addLast(data);
         return;
         }
         ListNode cur=search(index);
         ListNode listNode=new ListNode(data);
         listNode.next=cur;
         cur.prev.next=listNode;
         listNode.prev=cur.prev;
         cur.prev=listNode;
     }
     public void removeFirst(int key){
         ListNode cur=head;
         while (cur!=null){
             if (cur.val==key){
                 //删除头节点
                 if (cur==head){
                      head=head.next;
                      if (head!=null){
                          head.prev=null;
                      }else {
                          last=null;
                      }
                 }else {
                     //删除wei节点
                     if (cur.next==null){
                         last=last.prev;
                         last.next=null;
                     }else {
                         //删除中间的
                         cur.prev.next=cur.next;
                         cur.next.prev=cur.prev;
                     }
                 }
                 return;
             }
             cur=cur.next;
         }


     }
    public void removeAll(int key){
        ListNode cur=head;
        while (cur!=null){
            if (cur.val==key){
                //删除头节点
                if (cur==head){
                    head=head.next;
                    if (head!=null){
                        head.prev=null;
                    }else {
                        last=null;
                    }
                }else {
                    //删除wei节点
                    if (cur.next==null){
                        last=last.prev;
                        last.next=null;
                    }else {
                        //删除中间的
                        cur.prev.next=cur.next;
                        cur.next.prev=cur.prev;
                    }
                }
               // return;
            }
            cur=cur.next;
        }


    }
     public void display(){
         ListNode cur=head;
         while (cur!=null){
             System.out.print(cur.val+" ");
             cur=cur.next;
         }
         System.out.println();
     }
     //查找key关键字是否在链表当中
     public boolean contains(int key){
         ListNode cur=head;
         while (cur!=null){
             if (cur.val==key){
                 return true;
             }
             cur= cur.next;
         }
         return false;
     }
     public ListNode search(int index){
         ListNode cur=head;
         while (index!=0){
             cur=cur.next;
             index--;
         }
         return cur;
     }
     public int size(){
         ListNode cur=head;
         int size=0;
         while (cur!=null){
        size++;
        cur=cur.next;
         }
         return size;
     }
     public void clear(){
         ListNode cur=head;
         while (cur!=null){
             ListNode cuen=cur.next;
             cur.prev=null;
             cur.next=null;
             cur=cuen;

         }
         head=null;
         last=null;
     }

}
